package leetcode.code1656;

import java.util.ArrayList;
import java.util.List;

public class OrderedStream2 {

	int ptr;

	String[] values;

	int maxLen, maxId;

	int n;

	Integer[] starts;
	int[] lens;

	public OrderedStream2(int n) {
		values = new String[n + 1];
		starts = new Integer[n + 1];
		lens = new int[n + 1];
		ptr = 1;
		maxId = 1;
		this.n = n;
	}

	public List<String> insert(int idKey, String value) {
		values[idKey] = value;
		update(idKey);
		List<String> ans = new ArrayList<>();
		if (idKey == ptr) {
			int p = maxId;
			while (p <= n && values[p] != null) {
				ans.add(values[p++]);
			}
			ptr = p;
		}
		return ans;
	}

	private void update(int idKey) {
		if (idKey > 0 && starts[idKey - 1] != null) {
			starts[idKey] = starts[idKey - 1];
			lens[starts[idKey]] += 1;
			lens[idKey] = lens[starts[idKey]];
		} else {
			starts[idKey] = idKey;
			lens[idKey] = 1;
		}
		if (idKey < n && starts[idKey + 1] != null) {
			int len = lens[idKey] + lens[idKey + 1];
			int tail = Math.min(n, idKey + lens[idKey + 1]);
			lens[tail] = len;
			starts[tail] = starts[idKey];
			lens[starts[idKey]] = len;
		}
 		if (lens[idKey] >= maxLen) {
			maxLen = lens[idKey];
			maxId = starts[idKey];
		}
	}
	
	public static void main(String[] args) {
		OrderedStream2 os= new OrderedStream2(5);
		os.insert(3, "ccccc"); // 插入 (3, "ccccc")，返回 []
		os.insert(1, "aaaaa"); // 插入 (1, "aaaaa")，返回 ["aaaaa"]
		os.insert(2, "bbbbb"); // 插入 (2, "bbbbb")，返回 ["bbbbb", "ccccc"]
		os.insert(5, "eeeee"); // 插入 (5, "eeeee")，返回 []
		os.insert(4, "ddddd"); // 插入 (4, "ddddd")，返回 ["ddddd", "eeeee"]


	}

}
